import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = { 5, 3, 8, 4, 2, 7, 1, 6 };
        System.out.println("Before sorting: " + IntStream.of(arr).boxed().collect(Collectors.toList()));
        shellSort(arr);
        System.out.println("After sorting: " + IntStream.of(arr).boxed().collect(Collectors.toList()));
    }

    public static void shellSort(int[] arr) {
        int n = arr.length;
        int gap = 1;
        // Find the gap value
        while (gap < n / 3) {
            gap = 3 * gap + 1;
        }
        while (gap > 0) {
            for(int i = gap; i < n; i++) {
                int temp = arr[i]; // save the current element
                int j;
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                    arr[j] = arr[j - gap]; // shift the element to the right
                }
                arr[j] = temp; // put the saved element in its correct position
            }
            gap /= 3;
        }
    }
}
